C. Basil's Garden

一排有 $n$ 朵花，其中 $i$ 朵花的正高度为 $h_{i}$ 米。

每一秒钟，从 $1$ 到 $n$ 的每一朵 $i$ 都会按以下顺序发生以下情况：

如果是 $i = n$ 或 $h_{i} > h_{i + 1}$ ， $h_{i}$ 的值会变为 $max (0, h_{i} - 1)$ 。

在所有 $1 \leq i \leq n$ 的 $h_{i} = 0$ 第一次出现之前，会经过多少秒？

短期当前

Note

给定 n 朵花，每秒有风吹过来使得 hi > hi+1 的花高度减一，问经过多长时间所有花的高度降低为 0。
那么对于第 i 朵花，如果其高度 hi <=hi+1则其高度降低为零用时为hi+1+1；如果其高度hi> hi+1，那么第 i 朵花高度降低为零的时间为 max (hi+1+1, hi)。
证明：
① hi <= hi+1，则第 i+1 朵花先降低至与第 i 朵花相同的高度，用时 hi+1-hi，此时，若第 i+1 朵花是最后一朵或 hi+2 < hi+1，那么第 i+1 朵花，花费单位时间，降低 1，此时满足 hi <= hi+1，则剩下的时间就是第 i 朵花降低为零的时间，为 hi，所以，总用时为 hi+1+1;
② hi > hi+1，如果，hi+1 为最后一朵，那么用时 hi；反之，hi+1 不是最后一朵，则第 i 朵花花费 hi-hi+1 的时间降低至与第 i+1 朵花相同高度，之后花费 1 个时间将 hi+1 降低 1，之后花费 hi 的时间降低为零，总用时为 max (hi+1+1, hi)。

void solve() {
    int n;cin >> n;
    vector<int> a(n + 1);
    for (int i = 1;i <= n;i++)cin >> a[i];
    int ans = a[n];
    for (int i = n - 1;i >= 1;i--) {
        ans = max(ans + 1, a[i]);
    }
    cout << ans << '\n';
}